public class No036 {
    /**
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
     * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
     */
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    static TreeNode lastNode = null;

    public static TreeNode Convert(TreeNode pRootOfTree) {
        ConvertNode(pRootOfTree);
        // 返回链表头节点
        while (lastNode != null && lastNode.left != null) {
            lastNode = lastNode.left;
        }
        return lastNode;
    }

    // 中序遍历
    public static void ConvertNode(TreeNode root) {
        if (root == null)
            return;
        ConvertNode(root.left);
        root.left = lastNode;
        if (lastNode != null)
            lastNode.right = root;
        lastNode = root;
        ConvertNode(root.right);
    }
}
